package 常见算法.优先级队列堆;

import java.util.*;

/**
 * @Date 2024/6/20 20:32
 * @description: 前k个高频单词
 * .        https://leetcode.cn/problems/top-k-frequent-words/
 * @Author LittleNight
 */
public class likou692 {


    public static void main(String[] args) {
        char ch = 'a';
        // 转为 ascii 码值
        System.out.println(ch - 0);
        System.out.println((int)ch);
    }

    // 小根堆
    // 因为维护一个大小为 K 的小根堆，堆顶元素是其中最小的 每次都把最小的元素弹出这样最后剩下的就是 K 个最大的元素了，时间复杂度NlogK，
    // 如果用大根堆，就需要全部元素 N 都进去。然后从大根堆再弹出 前K个 这样时间复杂度是 NlogN。区别在于我们需要维护堆的元素数量，这个数量决定了我们每次取最值元素的时间复杂度

    // 练习
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        Map<String, Integer> hashMap = new HashMap<>();
        for(String s : words) {
            hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
        }
        // 2.创建小跟堆
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
            if(a.getValue() == b.getValue()) {
                // value 是次数, 次数相同, 按照字典序. 从小到大. 求字典序最小的. 相当于是大跟堆
                return b.getKey().compareTo(a.getKey());
            }
            // 次数. 小根堆
            // 两种写法都可以
            // return a.getValue() - b.getValue();
            return a.getValue().compareTo(b.getValue());
        });
        // 3. TopK的主逻辑
        // 遍历添加元素, 如果超过 size, 弹出栈顶元素
        // 一定要学会遍历 map
        // 一定要学会遍历 map
        // 一定要学会遍历 map
        for(Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            heap.offer(entry);
            if(heap.size() > k) {
                heap.poll(); // 弹出栈顶元素
            }
        }
        // 4. 收集结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            String tmp = heap.poll().getKey(); // 注意还要 getKey()
            ret.add(tmp);
        }
        // 逆置
        Collections.reverse(ret);
        return ret;

    }


    //力扣692.前k个高频单词(中等题目)  用peek
    public List<String> topKFrequent2(String[] words, int k) {
        //1、遍历数组 统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s,hashMap.getOrDefault(s,0) + 1);
        }

        //2.相当于求前k大的，要建立小根堆
        /**
         *   注意这里我们要进行比较的是Map.Entry<String,Integer>中的次数进行比较，
         Map.Entry<String,Integer> 是 Map 实现用来存放 k-v 映射键值对的内部类
         *   所以我们要传入一个比较器
         */
        Queue<Map.Entry<String,Integer>> minHeap = new PriorityQueue(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果次数相等的话，则进行比较字母前后，也就相当于建了一个大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //遍历hashMap
        for (Map.Entry<String, Integer> entry: hashMap.entrySet()) {
            /**
             * 特别注意，这里是<k   而不是小于等于，因为size = 0的时候就执行了一次offer了
             */
            if (minHeap.size() < k) {
                minHeap.offer(entry);   //放入了前k个元素
            } else {
                //Map.Entry<String, Integer> top = minHeap.peek();
                //如果堆顶元素次数小于遍历的，则进行替换
                if(minHeap.peek().getValue().compareTo(entry.getValue()) < 0 ) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //这是次数相同的情况下，进行比较单词
                    //Map.Entry<String, Integer> top = minHeap.peek();
                    if (minHeap.peek().getValue().compareTo(entry.getValue()) == 0) {
                        if(minHeap.peek().getKey().compareTo(entry.getKey()) > 0) {
                            //如果遍历到的单词字母靠前的话，则与堆顶元素进行替换
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //走到这之后，小根堆中已经有了元素，依次弹出到一个数组中去
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String ch = minHeap.poll().getKey();
            list.add(ch);
        }
        //注意这是小根堆进行弹出的，所以是从小到大的，要进行反转，变成从大到小的
        Collections.reverse(list);   //这是一个专门处理集合的，类似于Arrays去处理数组的
        return list;
    }

}
